// 检查s[l, r]之间括号是否完全匹配
int check(char *s, int l, int r) {
    int len = r - l + 1;
    char str[len]; 
    int top = -1;

    for (int i = l; i <= r; i++) {
        if (top == -1 || s[i] == '(') str[++top] = s[i];
        else if (s[i] == ')' && str[top] == '(') {
            top--;
        }
    }
    return (top == -1);
}

int longestValidParentheses(char * s) {
    int len = strlen(s);
    if (len == 0) return 0;

    int dp[len];	// dp[i]表示以i为末尾的最长有效号数量 
    for (int i = 0; i < len; i++) dp[i] = 0;
    dp[0] = 0;
    
	// 动态规划的思想是记忆化搜索和递推；
	// 而现在对几乎每种情况都要检查一次，这不是暴力法吗？？？
	// 运行超时，动态规划的错误示范。。。
    for (int i = 1; i < len; i++) {
        int max = 0; 
        for (int j = 0; j < i; j++) {
            int check_len = i - j + 1;
            if (check_len <= max) break;

            if (check(s, j, i)) {
                max = fmax(max, check_len);
            }
        }
        dp[i] = fmax(dp[i-1], max);
    }
    
    return dp[len - 1];
}